home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / applications / misc / pcal-4.5.lha / pcal / exprpars.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-16  |  8.4 KB  |  385 lines
  1. /*
  2.  * exprpars.c - Pcal routines concerned with parsing if{n}def expressions
  3.  *
  4.  * Contents:
  5.  *
  6.  *        do_xxx
  7.  *        lookup_token
  8.  *        next_token
  9.  *        parse_expr
  10.  *
  11.  * Revision history:
  12.  *
  13.  *    4.5    AWR    04/28/93    restructure function definitions so
  14.  *                    function name appears in first column
  15.  *                    (to facilitate searching for definition
  16.  *                    by name)
  17.  *
  18.  *    4.0    AWR    02/06/91    Author
  19.  *
  20.  */
  21.  
  22. /*
  23.  * Standard headers:
  24.  */
  25.  
  26. #include <ctype.h>
  27. #include <string.h>
  28. #include <stdio.h>
  29.  
  30. /*
  31.  * Pcal-specific definitions:
  32.  */
  33.  
  34. #include "pcaldefs.h"
  35. #include "pcalglob.h"
  36.  
  37. /*
  38.  * Macros:
  39.  */
  40.  
  41. /*
  42.  * token type code definitions:
  43.  */
  44.  
  45. #define TK_UNKNOWN     0        /* codes returned by next_token() */
  46. #define TK_IDENT     1
  47. #define TK_LPAREN     2
  48. #define TK_RPAREN     3
  49. #define TK_UNARYOP     4
  50. #define TK_BINARYOP     5
  51. #define TK_ENDINPUT     6
  52. #define TK_STARTINPUT     7        /* special code for start symbol */
  53.  
  54. /* bit position for token type codes (cf. where_ok[] below) */
  55. #define ID_OK        (1 << TK_IDENT)
  56. #define LP_OK        (1 << TK_LPAREN)
  57. #define RP_OK        (1 << TK_RPAREN)
  58. #define UO_OK        (1 << TK_UNARYOP)
  59. #define BO_OK        (1 << TK_BINARYOP)
  60. #define ST_OK        (1 << TK_STARTINPUT)
  61. #define NEVER_OK    0
  62.  
  63. /* is token "curr" legal after "prev"? (cf. where_ok[] below) */
  64. #define IS_LEGAL(curr, prev)    (where_ok[curr] & (1 << (prev)))
  65.  
  66. /*
  67.  * operator-related definitions:
  68.  */
  69.  
  70. #define OP_AND        0    /* operator subcodes */
  71. #define OP_OR        1
  72. #define OP_XOR        2
  73. #define OP_NEGATE    3
  74.  
  75. #define ENDINPUT_PREC    -1    /* arbitrary number < lowest op. prec  */
  76. #define OR_PREC         1    /* operator precedence levels */
  77. #define XOR_PREC     2
  78. #define AND_PREC     3
  79. #define NEGATE_PREC     4
  80. #define PAREN_PREC     8    /* arbitrary number > highest op. prec */
  81.  
  82. /* lower bits of operator stack entry are code; higher are precedence */
  83. #define OPR_BITS    4
  84. #define OPR_MASK    ((1 << OPR_BITS) - 1)
  85. #define PREC(op)    ((op) >> OPR_BITS)
  86. #define OPCODE(op)    ((op) & OPR_MASK)
  87. #define MAKE_OPR(p, o)    (((p) << OPR_BITS) | (o))
  88.  
  89. #define MAX_OP        20    /* size of operand and operator stacks */
  90.  
  91. /*
  92.  * Globals:
  93.  */
  94.  
  95. typedef short OPERAND;        /* types for operand and operator stacks */
  96. typedef short OPERATOR;
  97.  
  98.  
  99. typedef struct {
  100.     char    *name;        /* token spelling */
  101.     short    type;        /* token type code */
  102.     short    value;        /* associated value */
  103.     } TOKEN;
  104.  
  105. /* token table - note that substrings must follow longer strings */
  106.  
  107. TOKEN token_tbl[] = {
  108.     "&&",    TK_BINARYOP,    OP_AND,        /* synonym for "&" */
  109.     "&",    TK_BINARYOP,    OP_AND,
  110.     "||",    TK_BINARYOP,    OP_OR,        /* synonym for "|" */
  111.     "|",    TK_BINARYOP,    OP_OR,
  112.     "!",    TK_UNARYOP,    OP_NEGATE,
  113.     "^",    TK_BINARYOP,    OP_XOR,
  114.     "(",    TK_LPAREN,    0,
  115.     ")",    TK_RPAREN,    0,
  116.     NULL,    TK_UNKNOWN,    0        /* must be last entry */
  117.     };
  118.  
  119.  
  120. typedef struct {
  121.     short prec;        /* precedence */
  122.     short type;        /* token type (TK_UNARYOP or TK_BINARYOP) */
  123. #ifdef PROTOS
  124.     OPERAND (*pfcn)(OPERAND *);    /* dispatch function */
  125. #else
  126.     OPERAND (*pfcn)();        /* dispatch function */
  127. #endif
  128.     } OPR;
  129.  
  130. /* operator table - entries must be in same order as OP_XXX */
  131.  
  132. #ifdef PROTOS
  133. static OPERAND do_and(OPERAND *);
  134. static OPERAND do_or(OPERAND *);
  135. static OPERAND do_xor(OPERAND *);
  136. static OPERAND do_negate(OPERAND *);
  137. #else
  138. static OPERAND do_and(), do_or(), do_xor(), do_negate();   /* dispatch fcns */
  139. #endif
  140.  
  141. OPR opr_tbl[] = {
  142.     AND_PREC,    TK_BINARYOP,    do_and,        /* OP_AND    */
  143.     OR_PREC,    TK_BINARYOP,    do_or,        /* OP_OR    */
  144.     XOR_PREC,    TK_BINARYOP,    do_xor,        /* OP_XOR    */
  145.     NEGATE_PREC,    TK_UNARYOP,    do_negate    /* OP_NEGATE    */
  146.     };
  147.  
  148.  
  149. /* set of tokens which each token may legally follow (in TK_XXX order) */
  150.  
  151. int where_ok[] = {
  152.     NEVER_OK                                      ,     /* TK_UNKNOWN    */
  153.     ST_OK         | LP_OK         | UO_OK | BO_OK ,     /* TK_IDENT    */
  154.     ST_OK         | LP_OK         | UO_OK | BO_OK ,     /* TK_LPAREN    */
  155.             ID_OK | LP_OK | RP_OK                 ,     /* TK_RPAREN    */
  156.     ST_OK         | LP_OK                 | BO_OK ,     /* TK_UNARYOP    */
  157.             ID_OK         | RP_OK                 ,     /* TK_BINARYOP    */
  158.     ST_OK | ID_OK         | RP_OK                    /* TK_ENDINPUT    */
  159.     };
  160.  
  161.  
  162. /*
  163.  * do_xxx - dispatch functions for operators
  164.  */
  165.  
  166. static OPERAND
  167. #ifdef PROTOS
  168. do_and(OPERAND *ptop)
  169. #else
  170. do_and(ptop)
  171.     OPERAND *ptop;
  172. #endif
  173. {
  174.     return ptop[0] && ptop[-1];
  175. }
  176.  
  177.  
  178. static OPERAND
  179. #ifdef PROTOS
  180. do_or(OPERAND *ptop)
  181. #else
  182. do_or(ptop)
  183.     OPERAND *ptop;
  184. #endif
  185. {
  186.     return ptop[0] || ptop[-1];
  187. }
  188.  
  189.  
  190. static OPERAND
  191. #ifdef PROTOS
  192. do_xor(OPERAND *ptop)
  193. #else
  194. do_xor(ptop)
  195.     OPERAND *ptop;
  196. #endif
  197. {
  198.     return (ptop[0] ^ ptop[-1]) != 0;
  199. }
  200.  
  201.  
  202. static OPERAND
  203. #ifdef PROTOS
  204. do_negate(OPERAND *ptop)
  205. #else
  206. do_negate(ptop)
  207.     OPERAND *ptop;
  208. #endif
  209. {
  210.     return ! ptop[0];
  211. }
  212.  
  213.  
  214. /*
  215.  * lookup_token - look up token in table; return pointer to table entry
  216.  */
  217. static TOKEN *
  218. #ifdef PROTOS
  219. lookup_token(char *p)
  220. #else
  221. lookup_token(p)
  222.     char *p;
  223. #endif
  224. {
  225.     TOKEN *ptok;
  226.  
  227.     for (ptok = token_tbl;
  228.          ptok->name && strncmp(p, ptok->name, strlen(ptok->name));
  229.          ptok++)
  230.         ;
  231.  
  232.     return ptok;
  233. }
  234.  
  235.  
  236. /*
  237.  * next_token - fetch next token from input string; fill in its type and value
  238.  * and return pointer to following character
  239.  */
  240. static char *
  241. #ifdef PROTOS
  242. next_token(char *p,
  243.        int *ptype,
  244.        int *pvalue)
  245. #else
  246. next_token(p, ptype, pvalue)
  247.     char *p;
  248.     int *ptype;
  249.     int *pvalue;
  250. #endif
  251. {
  252.     TOKEN *ptok;
  253.     char tokbuf[STRSIZ], *pb;
  254.  
  255. #define NT_RETURN(p, t, v) \
  256.     if (1) { *ptype = t; *pvalue = v; return p; } else
  257.  
  258.     while (*p && isspace(*p))    /* skip whitespace */
  259.         p++;
  260.  
  261.     if (*p == '\0')            /* end of input? */
  262.         NT_RETURN(p, TK_ENDINPUT, 0);
  263.  
  264.     if (isalpha(*p) || *p == '-') {        /* identifier or flag? */
  265.  
  266.         pb = tokbuf;        /* make local copy and look up */
  267.         while (*p && (isalpha(*p) || isdigit(*p) || *p == '_' ||
  268.                (pb == tokbuf && *p == '-')))
  269.             *pb++ = *p++;
  270.         *pb = '\0';
  271.  
  272.         NT_RETURN(p, TK_IDENT, find_sym(tokbuf));
  273.     }
  274.  
  275.     ptok = lookup_token(p);        /* other token */
  276.     NT_RETURN(p + (ptok->name ? strlen(ptok->name) : 1), ptok->type,
  277.         ptok->value);
  278. }
  279.  
  280.  
  281. /*
  282.  * parse_expr - parses expression consisting of identifiers and logical
  283.  * operators; return TRUE if expression is true (identifier defined => true);
  284.  * FALSE if false; EXPR_ERR if syntax error in expression
  285.  */
  286. int
  287. #ifdef PROTOS
  288. parse_expr(char *pbuf)
  289. #else
  290. parse_expr(pbuf)
  291.     char *pbuf;
  292. #endif
  293. {
  294.     OPERAND opd_stack[MAX_OP];    /* operand stack - TRUE/FALSE values */
  295.     OPERATOR opr_stack[MAX_OP];    /* operator stack - precedence | op */
  296.     int value, token, plevel, prec, result, npop, opr, opd, prev_token, op;
  297.  
  298.     plevel = 0;            /* paren nesting level */
  299.     opd = opr = -1;            /* indices of stack tops */
  300.     prev_token = TK_STARTINPUT;    /* to detect null expressions */
  301.  
  302.     if (DEBUG(DEBUG_PP))
  303.         FPR(stderr, "evaluating expression '%s'\n", pbuf);
  304.     do {
  305.         pbuf = next_token(pbuf, &token, &value);
  306.  
  307.         /* check that the current token may follow the previous one */
  308.         if (! IS_LEGAL(token, prev_token))
  309.             return EXPR_ERR;
  310.  
  311.         switch(token) {
  312.  
  313.         case TK_IDENT:        /* identifier => 1 if def, 0 if not */
  314.             opd_stack[++opd] = value != PP_SYM_UNDEF;
  315.             break;
  316.  
  317.         case TK_LPAREN:        /* left paren - bump nesting level */
  318.             ++plevel;
  319.             break;
  320.  
  321.         case TK_RPAREN:        /* right paren - decrement nesting */
  322.             if (--plevel < 0)
  323.                 return EXPR_ERR;
  324.             break;
  325.  
  326.         case TK_ENDINPUT:    /* end-of-input - treat as operator */
  327.             if (prev_token == TK_STARTINPUT)
  328.                 return FALSE;    /* null expr => FALSE */
  329.             /* fall through */
  330.  
  331.         case TK_UNARYOP:
  332.         case TK_BINARYOP:
  333.  
  334.             /* get precedence of operator, adjusting for paren
  335.              * nesting (TK_ENDINPUT has the lowest precedence
  336.              * of all, to unwind operand/operator stacks at end)
  337.              */
  338.  
  339.             prec = token == TK_ENDINPUT ? ENDINPUT_PREC :
  340.                 (plevel * PAREN_PREC) + opr_tbl[value].prec;
  341.  
  342.             /* pop (and perform) any equal- or higher-precedence
  343.              * operators on operator stack: extract operator,
  344.              * check for operand stack underflow, execute
  345.              * operator, adjust operand stack height and place
  346.              * result of operator on top
  347.              */
  348.  
  349.             for ( ;
  350.                  opr >= 0 && PREC(opr_stack[opr]) >= prec;
  351.                  opr--) {
  352.                 op = OPCODE(opr_stack[opr]);
  353.                 npop = opr_tbl[op].type == TK_UNARYOP ? 0 : 1;
  354.                 if (opd < npop)
  355.                     return EXPR_ERR;
  356.                 result = (*opr_tbl[op].pfcn)(opd_stack + opd);
  357.                 opd_stack[opd -= npop] = result;
  358.             }
  359.  
  360.             /* push operator (if any) onto stack */
  361.  
  362.             if (token != TK_ENDINPUT)
  363.                 opr_stack[++opr] = MAKE_OPR(prec, value);
  364.  
  365.             break;
  366.  
  367.         default:        /* should never get here */
  368.             return EXPR_ERR;
  369.             break;
  370.         }
  371.  
  372.         prev_token = token;
  373.  
  374.     } while (token != TK_ENDINPUT);
  375.  
  376.     /* done - check for dangling parens, and leftover operand/operators */
  377.  
  378.     if (DEBUG(DEBUG_PP))
  379.         FPR(stderr, "evaluated to %s\n", opd_stack[0] ? "TRUE" : "FALSE");
  380.     return plevel != 0 || opd != 0 || opr != -1 ?
  381.         EXPR_ERR :        /* leftover junk - return error */
  382.         opd_stack[0];        /* all OK - return final value */
  383. }
  384.  
  385.